package leetCode;

import java.util.ArrayList;
import java.util.List;

/**
 * 22 括号生成
 * 数组/递归/dfs

 数字 n代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

 示例 1：
 输入：n = 3
 输出：["((()))","(()())","(())()","()(())","()()()"]

 示例 2：
 输入：n = 1
 输出：["()"]

 提示：
 1 <= n <= 8
 */
public class GenerateParentheses {
    public static void main(String[] args) {
        System.out.println(generateParenthesis(3).toString());
    }

    static List<String> res = new ArrayList<>();

    //递归，很巧妙的解法，dfs，76/86
    public static List<String> generateParenthesis(int n) {
        generate(n,n,"");
        return res;
    }

    public static void generate(int left, int right, String ans) {
        if (left == 0 && right == 0) {
            res.add(ans);
            return;
        }
        if (left > 0) {
            generate(left-1, right, ans + "(");
        }
        if (right > left) {
            generate(left, right-1, ans + ")");
        }
    }
}
